// 版权归Go作者所有。版权所有。
// 此源代码的使用受BSD样式的约束
// 可以在许可证文件中找到的许可证。

// 此文件实现泛型类型的实例化
// 通过用实际值替换类型参数
// 类型。

package types2

import (
	"bytes"
	"cmd/compile/internal/syntax"
	"fmt"
)

type substMap struct {
	// *命名类型替换当前需要targs字段。
	// TODO（gri）重写该代码，去掉该字段，并使其
	// 仅构造映射（proj）
	targs []Type
	proj  map[*TypeParam]Type
}

// MakeSubsMap创建一个新的替换映射，将tpars[i]映射到targs[i]。
// 如果targs[i]为零，则不替换tpars[i]。
func makeSubstMap(tpars []*TypeName, targs []Type) *substMap {
	assert(len(tpars) == len(targs))
	proj := make(map[*TypeParam]Type, len(tpars))
	for i, tpar := range tpars {
		// 我们必须展开类型参数，否则为*instance
		// 类型最终成为复合类型中的组件。
		// TODO（gri）解释为什么这会导致问题，如果是这样的话
		targ := expand(targs[i]) // 可能是零
		targs[i] = targ
		proj[tpar.typ.(*TypeParam)] = targ
	}
	return &substMap{targs, proj}
}

func (m *substMap) String() string {
	return fmt.Sprintf("%s", m.proj)
}

func (m *substMap) empty() bool {
	return len(m.proj) == 0
}

func (m *substMap) lookup(tpar *TypeParam) Type {
	if t := m.proj[tpar]; t != nil {
		return t
	}
	return tpar
}

func (check *Checker) instantiate(pos syntax.Pos, typ Type, targs []Type, poslist []syntax.Pos) (res Type) {
	if check.conf.Trace {
		check.trace(pos, "-- instantiating %s with %s", typ, typeListString(targs))
		check.indent++
		defer func() {
			check.indent--
			var under Type
			if res != nil {
				// 在（）下调用可能会导致无休止的实例化。
				// 测试用例：类型T[P any]T[P]
				// TODO（gri）调查这是否是一个bug或预期的问题。
				under = res.Underlying()
			}
			check.trace(pos, "=> %s (under = %s)", res, under)
		}()
	}

	assert(len(poslist) <= len(targs))

	// TODO（gri）这里什么更好：使用TypeParams，还是使用TypeName？
	var tparams []*TypeName
	switch t := typ.(type) {
	case *Named:
		tparams = t.tparams
	case *Signature:
		tparams = t.tparams
		defer func() {
			// 如果我们在某个地方发生了意外的失败，不要惊慌失措
			// 断言物（*签名）。检查*签名，以防类型[无效]
			// 他回来了。
			if _, ok := res.(*Signature); !ok {
				return
			}
			// 如果签名不使用其类型参数，则subst
			// 不会复制。在这种情况下，现在就复制一份（所以
			// 我们可以将tparams设置为零（不产生副作用）。
			if t == res {
				copy := *t
				res = &copy
			}
			// 实例化泛型签名后，它不是泛型的
			// 不再我们需要将tparams设置为零。
			res.(*Signature).tparams = nil
		}()

	default:
		check.dump("%v: cannot instantiate %v", pos, typ)
		unreachable() // 只有已定义的类型和（已定义的）函数才能为泛型

	}

	// 提供的类型数必须与类型参数数匹配
	if len(targs) != len(tparams) {
		// TODO（gri）提供更好的错误消息
		check.errorf(pos, "got %d arguments but %d type parameters", len(targs), len(tparams))
		return Typ[Invalid]
	}

	if len(tparams) == 0 {
		return typ // 无事可做（小优化）
	}

	smap := makeSubstMap(tparams, targs)

	// 检查边界
	for i, tname := range tparams {
		tpar := tname.typ.(*TypeParam)
		iface := tpar.Bound()
		if iface.Empty() {
			continue // 无类型限制
		}

		targ := targs[i]

		// 错误报告的最佳位置
		pos := pos
		if i < len(poslist) {
			pos = poslist[i]
		}

		// 类型参数绑定使用相同的类型参数进行参数化
		// 作为实例化类型；在使用它进行边界检查之前，我们需要
		// 需要使用我们实例化的类型参数来实例化它
		// 参数化类型。
		iface = check.subst(pos, iface, smap).(*Interface)

		// targ必须实施iface（方法）
		// -只有当我们有方法时才检查
		check.completeInterface(nopos, iface)
		if len(iface.allMethods) > 0 {
			// 如果类型参数是指向类型参数的指针，则类型参数的
			// 方法集为空。
			// TODO（gri）这是我们想要的吗？（规格问题）
			if base, isPtr := deref(targ); isPtr && asTypeParam(base) != nil {
				check.errorf(pos, "%s has no methods", targ)
				break
			}
			if m, wrong := check.missingMethod(targ, iface, true); m != nil {
				// TODO（gri）需要打印更新的名称，以避免错误消息中出现重大混乱！
				// （暂时打印警告）
				// 旧警告：
				// 检查.SoftError（位置，“%s不满足%s（警告：名称未更新）=%s（缺少方法%s）”，目标，tpar.bound，iface，m）
				if m.name == "==" {
					// 我们不想报告“缺少方法==”。
					check.softErrorf(pos, "%s does not satisfy comparable", targ)
				} else if wrong != nil {
					// TODO（gri）这仍然可以报告生成错误消息的未实例化类型
					// 比必要的时候更难阅读。
					check.softErrorf(pos,
						"%s does not satisfy %s: wrong method signature\n\tgot  %s\n\twant %s",
						targ, tpar.bound, wrong, m,
					)
				} else {
					check.softErrorf(pos, "%s does not satisfy %s (missing method %s)", targ, tpar.bound, m.name)
				}
				break
			}
		}

		// targ的基础类型也必须是列出的接口类型之一（如果有）
		if iface.allTypes == nil {
			continue // 无事可做
		}

		// 如果targ本身是一个类型参数，则其每个可能的类型（但至少有一个）都必须位于
		// iface类型列表（即targ类型列表必须是iface类型的非空子集）。
		if targ := asTypeParam(targ); targ != nil {
			targBound := targ.Bound()
			if targBound.allTypes == nil {
				check.softErrorf(pos, "%s does not satisfy %s (%s has no type constraints)", targ, tpar.bound, targ)
				break
			}
			for _, t := range unpack(targBound.allTypes) {
				if !iface.isSatisfiedBy(t) {
					// TODO（gri）将此错误消息与下面的消息匹配（反之亦然）
					check.softErrorf(pos, "%s does not satisfy %s (%s type constraint %s not found in %s)", targ, tpar.bound, targ, t, iface.allTypes)
					break
				}
			}
			break
		}

		// 否则，targ的类型或基础类型也必须是列出的接口类型之一（如果有）。
		if !iface.isSatisfiedBy(targ) {
			check.softErrorf(pos, "%s does not satisfy %s (%s not found in %s)", targ, tpar.bound, under(targ), iface.allTypes)
			break
		}
	}

	return check.subst(pos, typ, smap)
}

// subst返回类型typ，其类型参数tpars替换为
// 相应的类型参数以递归方式指向。
// subst的功能在于它不修改传入的
// 类型如果发生替换，则结果类型与
// 从传入类型。
func (check *Checker) subst(pos syntax.Pos, typ Type, smap *substMap) Type {
	if smap.empty() {
		return typ
	}

	// 常见案例
	switch t := typ.(type) {
	case *Basic:
		return typ // 无事可做
	case *TypeParam:
		return smap.lookup(t)
	}

	// 一般情况
	subst := subster{check, pos, make(map[Type]Type), smap}
	return subst.typ(typ)
}

type subster struct {
	check *Checker
	pos   syntax.Pos
	cache map[Type]Type
	smap  *substMap
}

func (subst *subster) typ(typ Type) Type {
	switch t := typ.(type) {
	case nil:
		// 如果typ可能为nil，则调用typernil。
		panic("nil typ")

	case *Basic, *bottom, *top:
		// 无事可做

	case *Array:
		elem := subst.typOrNil(t.elem)
		if elem != t.elem {
			return &Array{len: t.len, elem: elem}
		}

	case *Slice:
		elem := subst.typOrNil(t.elem)
		if elem != t.elem {
			return &Slice{elem: elem}
		}

	case *Struct:
		if fields, copied := subst.varList(t.fields); copied {
			return &Struct{fields: fields, tags: t.tags}
		}

	case *Pointer:
		base := subst.typ(t.base)
		if base != t.base {
			return &Pointer{base: base}
		}

	case *Tuple:
		return subst.tuple(t)

	case *Signature:
		// TODO（gri）重新考虑recv在参数化类型方法方面的情况
		// recv:=子变量（t.recv）
		recv := t.recv
		params := subst.tuple(t.params)
		results := subst.tuple(t.results)
		if recv != t.recv || params != t.params || results != t.results {
			return &Signature{
				rparams: t.rparams,
				// TODO（gri）为什么我们不能在这里将tparams归零，而不是在
				// 在上面举例？
				tparams:  t.tparams,
				scope:    t.scope,
				recv:     recv,
				params:   params,
				results:  results,
				variadic: t.variadic,
			}
		}

	case *Sum:
		types, copied := subst.typeList(t.types)
		if copied {
			// 不要使用Sum-literal手动执行此操作：新
			// 类型列表可能不唯一，NewSum可能会删除
			// 复制品。
			return NewSum(types)
		}

	case *Interface:
		methods, mcopied := subst.funcList(t.methods)
		types := t.types
		if t.types != nil {
			types = subst.typ(t.types)
		}
		embeddeds, ecopied := subst.typeList(t.embeddeds)
		if mcopied || types != t.types || ecopied {
			iface := &Interface{methods: methods, types: types, embeddeds: embeddeds}
			if subst.check == nil {
				panic("internal error: cannot instantiate interfaces yet")
			}
			subst.check.posMap[iface] = subst.check.posMap[t] // 满足完全接口要求
			subst.check.completeInterface(nopos, iface)
			return iface
		}

	case *Map:
		key := subst.typ(t.key)
		elem := subst.typ(t.elem)
		if key != t.key || elem != t.elem {
			return &Map{key: key, elem: elem}
		}

	case *Chan:
		elem := subst.typ(t.elem)
		if elem != t.elem {
			return &Chan{dir: t.dir, elem: elem}
		}

	case *Named:
		// 转储用于调试
		dump := func(string, ...interface{}) {}
		if subst.check != nil && subst.check.conf.Trace {
			subst.check.indent++
			defer func() {
				subst.check.indent--
			}()
			dump = func(format string, args ...interface{}) {
				subst.check.trace(subst.pos, format, args...)
			}
		}

		if t.tparams == nil {
			dump(">>> %s is not parameterized", t)
			return t // 类型未参数化
		}

		var new_targs []Type

		if len(t.targs) > 0 {
			// 已经实例化
			dump(">>> %s already instantiated", t)
			assert(len(t.targs) == len(t.tparams))
			// 对于每个（现有）类型参数targ，确定是否需要
			// 待替换；i、 例如，如果是或包含类型参数
			// 它有一个类型参数。
			for i, targ := range t.targs {
				dump(">>> %d targ = %s", i, targ)
				new_targ := subst.typ(targ)
				if new_targ != targ {
					dump(">>> substituted %d targ %s => %s", i, targ, new_targ)
					if new_targs == nil {
						new_targs = make([]Type, len(t.tparams))
						copy(new_targs, t.targs)
					}
					new_targs[i] = new_targ
				}
			}

			if new_targs == nil {
				dump(">>> nothing to substitute in %s", t)
				return t // 无可替代
			}
		} else {
			// 尚未实例化
			dump(">>> first instantiation of %s", t)
			new_targs = subst.smap.targs
		}

		// 在创建新的命名类型之前，请检查是否已经有了此类型
		h := instantiatedHash(t, new_targs)
		dump(">>> new type hash: %s", h)
		if subst.check != nil {
			if named, found := subst.check.typMap[h]; found {
				dump(">>> found %s", named)
				subst.cache[t] = named
				return named
			}
		}

		// 创建新的命名类型并填充缓存以避免无休止的递归
		tname := NewTypeName(subst.pos, t.obj.pkg, t.obj.name, nil)
		named := subst.check.newNamed(tname, t, t.underlying, t.tparams, t.methods) // 方法签名被延迟更新
		named.targs = new_targs
		if subst.check != nil {
			subst.check.typMap[h] = named
		}
		subst.cache[t] = named

		// 代用
		dump(">>> subst %s with %s (new: %s)", t.underlying, subst.smap, new_targs)
		named.underlying = subst.typOrNil(t.underlying)
		named.fromRHS = named.underlying // 用于周期检测（Checker.validType）

		return named

	case *TypeParam:
		return subst.smap.lookup(t)

	case *instance:
		// TODO（gri）是否可以避免此处的扩展，而只替换类型参数？
		return subst.typ(t.expand())

	default:
		unimplemented()
	}

	return typ
}

// TODO（gri）最终，这应该更加复杂。
// 对于本地声明的类型，它无法正常工作。
func instantiatedHash(typ *Named, targs []Type) string {
	var buf bytes.Buffer
	writeTypeName(&buf, typ.obj, nil)
	buf.WriteByte('[')
	writeTypeList(&buf, targs, nil, nil)
	buf.WriteByte(']')

	// 对于表示的类型，是否
	// 类型完全展开或存储为实例
	// 没关系——它们是相同的类型。
	// 删除为实例打印的instanceMarkers。
	res := buf.Bytes()
	i := 0
	for _, b := range res {
		if b != instanceMarker {
			res[i] = b
			i++
		}
	}

	return string(res[:i])
}

func typeListString(list []Type) string {
	var buf bytes.Buffer
	writeTypeList(&buf, list, nil, nil)
	return buf.String()
}

// typernil类似于typ，但如果参数为nil，则替换为typ[Invalid]。
// nil型可能出现在病理性病例中，如T型[P any][]func（T（[]uu））
// 在设置数组/切片元素之前访问它的位置。
func (subst *subster) typOrNil(typ Type) Type {
	if typ == nil {
		return Typ[Invalid]
	}
	return subst.typ(typ)
}

func (subst *subster) var_(v *Var) *Var {
	if v != nil {
		if typ := subst.typ(v.typ); typ != v.typ {
			copy := *v
			copy.typ = typ
			return &copy
		}
	}
	return v
}

func (subst *subster) tuple(t *Tuple) *Tuple {
	if t != nil {
		if vars, copied := subst.varList(t.vars); copied {
			return &Tuple{vars: vars}
		}
	}
	return t
}

func (subst *subster) varList(in []*Var) (out []*Var, copied bool) {
	out = in
	for i, v := range in {
		if w := subst.var_(v); w != v {
			if !copied {
				// 被替换的第一个变量=>allocate new out slice
				// 并复制所有变量
				new := make([]*Var, len(in))
				copy(new, out)
				out = new
				copied = true
			}
			out[i] = w
		}
	}
	return
}

func (subst *subster) func_(f *Func) *Func {
	if f != nil {
		if typ := subst.typ(f.typ); typ != f.typ {
			copy := *f
			copy.typ = typ
			return &copy
		}
	}
	return f
}

func (subst *subster) funcList(in []*Func) (out []*Func, copied bool) {
	out = in
	for i, f := range in {
		if g := subst.func_(f); g != f {
			if !copied {
				// 被替换的第一个函数=>allocate new out slice
				// 并复制所有功能
				new := make([]*Func, len(in))
				copy(new, out)
				out = new
				copied = true
			}
			out[i] = g
		}
	}
	return
}

func (subst *subster) typeList(in []Type) (out []Type, copied bool) {
	out = in
	for i, t := range in {
		if u := subst.typ(t); u != t {
			if !copied {
				// 被替换的第一个函数=>allocate new out slice
				// 并复制所有功能
				new := make([]Type, len(in))
				copy(new, out)
				out = new
				copied = true
			}
			out[i] = u
		}
	}
	return
}
